# -*- coding: utf-8 -*-
# Created by zhangyanqi on 2018/4/26

"""
使用递归和非递归遍历二叉树
"""
class TreeNode(object):
    def __init__(self, val, l, r):
        self.val = val
        self.right = r
        self.left = l

    def __str__(self):
        return str(self.val)


# 递归 Recursion
def pre_order_traversal_recursion(root):
    if root is None:
        return
    print(root.val)
    pre_order_traversal_recursion(root.left)
    pre_order_traversal_recursion(root.right)


def in_order_traversal_recursion(root):
    if root is None:
        return
    in_order_traversal_recursion(root.left)
    print(root.val)
    in_order_traversal_recursion(root.right)


def post_order_traversal_recursion(root):
    if root is None:
        return
    post_order_traversal_recursion(root.left)
    post_order_traversal_recursion(root.right)
    print(root.val)


# 非递归
def pre_order_traversal_without_recursion(root):
    l = []
    while root is not None or len(l) != 0:
        if root is not None:
            print(root.val)
            l.append(root)
            root = root.left
        else:
            pop = l.pop(len(l) - 1)
            root = pop.right


def in_order_traversal_without_recursion(root):
    l = []
    while root is not None or len(l) != 0:
        if root is not None:
            l.append(root)
            root = root.left
        else:
            pop = l.pop(len(l) - 1)
            if pop is not None:
                print(pop.val)
                root = pop.right
            else:
                root = None


def post_order_traversal_without_recursion(root):
    l = []
    # 上一个右节点
    last = None
    while root is not None or len(l) > 0:
        # 向左走到尽头
        if root is not None:
            l.append(root)
            root = root.left
        else:
            p = l[len(l) - 1]
            if p.right is not None and p.right != last:
                root = p.right
                l.append(root)
                root = root.left
            else:
                pop = l.pop(len(l) - 1)
                print(pop.val)
                last = pop
                root = None


if __name__ == "__main__":
    node6 = TreeNode(6, None, None)
    node5 = TreeNode(5, None, None)
    node4 = TreeNode(4, None, None)
    node3 = TreeNode(3, node6, None)
    node2 = TreeNode(2, node4, node5)
    node1 = TreeNode(1, node2, node3)
    # pre_order_traversal_recursion(node1)
    # in_order_traversal_recursion(node1)
    # post_order_traversal_recursion(node1)
    # pre_order_traversal_without_recursion(node1)
    in_order_traversal_without_recursion(node1)
    # post_order_traversal_without_recursion(node1)
